import java.util.Arrays;

public class HeapDemo {
    public static void main(String[] args) {
        int arr[] = new int[]{9,8,7,6,5,4,3,2,1};
        int left = 0,right = arr.length-1;
        quickSort(arr,left,right);
        Arrays.stream(arr).forEach(System.out::print);

    }

    private static void quickSort(int[] arr, int left, int right) {
        int l = left+1,r = right;
        if(left>=right) return;
        int base = arr[left];
        while (true){
            while ( l<=r && arr[l] <= base) l++;
            while ( l<=r && arr[r]>=base) r--;
            if(l>r) break;
            if(l<r){
                int swap = arr[l];
                arr[l] = arr[r];
                arr[r] = swap;
            }
            l++;r--;
        }
        // 基准归位
//        if(arr[left]>arr[l]) {
            arr[left] = arr[r];
            arr[r] = base;
//        }
        quickSort(arr,left,r-1);
        quickSort(arr,r+1,right);
    }
}
